typedef struct TreeNode TreeNode;

// 定义栈节点
typedef struct StackNode {
    TreeNode* node;
    struct StackNode* next;
} StackNode;

// 压栈
void push(StackNode** top, TreeNode* node) {
    StackNode* new_node = (StackNode*)malloc(sizeof(StackNode));
    new_node->node = node;
    new_node->next = *top;
    *top = new_node;
}

// 弹栈
TreeNode* pop(StackNode** top) {
    if (*top == NULL) return NULL;
    StackNode* temp = *top;
    TreeNode* node = temp->node;
    *top = temp->next;
    free(temp);
    return node;
}

// 查看栈顶元素
TreeNode* peek(StackNode* top) {
    if (top == NULL) return NULL;
    return top->node;
}

// 判断栈是否为空
int isEmpty(StackNode* top) {
    return top == NULL;
}

// 交换两个指针
void swap(TreeNode** a, TreeNode** b) {
    TreeNode* temp = *a;
    *a = *b;
    *b = temp;
}

// 主函数：翻转二叉树
TreeNode* invertTree(TreeNode* root) {
    StackNode* stack = NULL;
    // 这个判断不能省略
    if (root != NULL) push(&stack, root);

    while (!isEmpty(stack)) {
        TreeNode* node = peek(stack);
        if (node != NULL) {
            // 模拟前序遍历
            pop(&stack);
            if (node->right) push(&stack, node->right);  // 右子树入栈
            if (node->left) push(&stack, node->left);    // 左子树入栈
            push(&stack, node);                          // 当前节点重新入栈
            push(&stack, NULL);                          // 用 NULL 作为标记
        } else {
            // 遇到 NULL，说明接下来的节点需要处理
            pop(&stack); // 弹出 NULL
            node = pop(&stack); // 弹出实际的节点
            swap(&(node->left), &(node->right)); // 翻转左右子树
        }
    }

    return root;
}
